class Solution {
    public static void main(String[] args) {
        int[] arr = {2, 4 , 1};
        System.out.println(maxProfit(2, arr));
    }
    public static int maxProfit(int k, int[] prices) {
        int len = prices.length ;
        int[][] f = new int[len][k+1] ;
        int[][] g = new int[len][k+1] ;
        f[0][0] = -prices[0] ; 
        for(int i=1 ; i <= k ; i ++){
            f[0][i] = -0x3f3f3f3f ;
            g[0][i] = -0x3f3f3f3f ;
        }
        for(int i=1 ; i < len ; i ++){
            for(int j=0 ; j <= k ; j ++){
                f[i][j] = Math.max(f[i-1][j] , g[i-1][j] - prices[i]) ; 
                g[i][j] = g[i-1][j] ;
                if(j-1>=0){
                    g[i][j] = Math.max(g[i-1][j] , f[i-1][j-1]+prices[i]) ;
                }
            }
        }
        int max = g[len-1][0] ; 
        for(int num : g[len-1]){
            if(max < num){
                max = num ;
            }
        }
      return max ;
    }
}